        #include "fata.h"
        #include "hashquad.h"
        #include <stdlib.h>

        #define MinTableSize (10)

        enum KindOfEntry { Legitimate, Empty, Deleted };

        struct HashEntry
        {
            ElementType Element;
            enum KindOfEntry Info;
        };

        typedef struct HashEntry Cell;

        /* Cell *TheCells will be an array of */
        /* HashEntry cells, allocated later */
        struct HashTbl
        {
            int TableSize;
            Cell *TheCells;
        };

        /* Return next prime; assume N >= 10 */
        static int
        NextPrime( int N )
        {
            int i;

            if ( N % 2 == 0 )
                N++;
            for ( ; ; N += 2 )
            {
                for ( i = 3; i * i < N; i += 2 )
                    if ( N % i == 0 )
                        goto ContOuter;
                return N;
                ContOuter: ;
            }
        }

        Index
        Hash( ElementType Key, int TableSize )
        {
            return Key % TableSize;
        }

/* START: fig5_15.txt */
        HashTable
        InitializeTable( int TableSize )
        {
            HashTable H;
            int i;

            if ( TableSize < MinTableSize )
            {
                Error( "Table size too small" );
                return NULL;
            }

            H = malloc( sizeof( struct HashTbl ) );
            if ( H == NULL )
                FataError( "Out of space" );
            
            H->TableSize = NextPrime( TableSize );

            H->TheCells = malloc( sizeof( Cell ) * H->TableSize );
            if ( H->TheCells == NULL )
                FataError( "Out of space" );

            for ( i = 0; i < H->TableSize; i++ )
                H->TheCells[i].Info = Empty;

            return H;
        }
/* END */

/* START: fig5_16.txt */
        Position
        Find( ElementType Key, HashTable H )
        {
            Position CurrentPos;
            int CollisionNum;

            CollisionNum = 0;
            CurrentPos = Hash( Key, H->TableSize );
            while ( H->TheCells[ CurrentPos ].Info != Empty &&
                    H->TheCells[ CurrentPos ].Element != Key ) /* Probably need strcmp!! */
            {
                /* F(i) = i * i ( i is CollisionNum ) equal to */
                /* F(i) = F(i - 1) + 2 * i - 1 */
                CurrentPos += 2 * ++CollisionNum - 1;
                if ( CurrentPos >= (Position)H->TableSize )
                    CurrentPos -= H->TableSize;
            }
            return CurrentPos;
        }
/* END */

/* START: fig5_17.txt */
        void
        Insert( ElementType Key, HashTable H )
        {
            Position Pos;

            Pos = Find( Key, H );
            if ( H->TheCells[ Pos ].Info != Legitimate )
            {
                H->TheCells[ Pos ].Info = Legitimate;
                H->TheCells[ Pos ].Element = Key; /* Probably need strcpy! */
            }
        }
/* END */

/* START: fig5_22.txt */
        HashTable
        Rehash( HashTable H )
        {
            int i, OldSize;
            Cell *OldCells;

            OldCells = H->TheCells;
            OldSize = H->TableSize;

            H = InitializeTable( 2 * OldSize );

            /* Scan through old table, reinserting into new */
            for ( i = 0; i < OldSize; i++ )
                if ( OldCells[ i ].Info == Legitimate )
                    Insert( OldCells[ i ].Element, H );

            free(OldCells);
            return H;
        }
/* END */

        ElementType
        Retrieve( Position P, HashTable H )
        {
            return H->TheCells[ P ].Element;
        }

        void
        DestroyTable( HashTable H )
        {
            free( H->TheCells );
            free( H );
        }

